#include "../tools.h"
#include "stdlib.h"

// 典型二维动态规划问题
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int size1 = text1.size();
        int size2 = text2.size();
        if(size1 == 0 || size2 == 0) return 0;

        // 用 +1，因为 dp 数组用 0 表示边界，text 数组的 0 表示第一个位置
        vector<vector<int>> dp(size1 + 1, vector<int>(size2 + 1, 0));

        for(int i = 0; i < size1; ++i){
            for(int j = 0; j < size2; ++j){
                if(text1[i] == text2[j])
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                else{
                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }
        // show(dp);
        return dp[size1][size2];
    }
};


int main(int argc, char const *argv[])
{
    
    string text1 = "abcde";
    string text2 = "c";

    Solution sol;

    cout << sol.longestCommonSubsequence(text1, text2) << endl;

    return 0;
}
